/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
  if (lists.length === 0) return null

  let interval = 1
  //当间隔小于链表长度时循环
  while (interval < lists.length) {
    //分治思想：两两合并
    for (let i = 0; i + interval < lists.length; i += interval * 2) {
      //调用归并函数
      lists[i] = mergeTwoLists(lists[i], lists[i + interval])
    }
    //一轮两两合并后，需要合并链表的间隔会翻倍
    interval = interval * 2
  }

  //返回链表0
  return lists[0]
};

//定义一个归并函数
function mergeTwoLists(list1, list2) {
  let dummy = new ListNode(0)
  let curr = dummy

  while (list1 && list2) {
    if (list1.val <= list2.val) {
      curr.next = list1
      list1 = list1.next
    } else {
      curr.next = list2
      list2 = list2.next
    }
    curr = curr.next
  }
  //curr指向剩余的链表
  curr.next = list1 || list2

  //返回头链表
  return dummy.next
}